package com.sjf.day02.Search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 二分查找  (递归实现)
 *
 * @author <huangtang>
 * @since 2021/12/29 15:11
 **/
public class BinarySearch {

    public static void main(String[] args) {

        int[] arr = {3,66,75,99,108,347,347,523};
        List<Integer> list = binarySearch2(arr, 347, 0, arr.length-1);

        if(list.get(0) == -1){
            System.out.println("不存在该数");
        }else{
            for (Integer integer : list) {
                System.out.print(arr[integer] +"\t");
            }
        }

    }

    /**
     * 二分查找，找到第一个满足的值返回下标
     * @param arr 查找的数组
     * @param val 查找的值
     * @param left 左边界
     * @param right 右边界
     * @return 找到 返回下标
     *         没找到 -1
     */
    public static int binarySearch(int[] arr,int val,int left,int right){
        if(left == right) return -1;
        int mid = (left+right)/2; //找到中间值的下标
        if(val < arr[mid] && left!=right){
            //向左边递归
            return binarySearch(arr,val,left,mid-1);
        }else if(val > arr[mid] && left!=right){
            return binarySearch(arr,val,mid+1,right);
        }else{
            return mid;
        }
    }

    /**
     * 二分查找，找到所有满足的值返回下标
     * @param arr 查找的数组
     * @param val 查找的值
     * @param left 左边界
     * @param right 右边界
     * @return 找到 返回下标
     *         没找到 -1
     */
    public static List<Integer> binarySearch2(int[] arr, int val, int left, int right){
        if(left == right) return Collections.singletonList(-1);
        int mid = (left+right)/2; //找到中间值的下标
        if (val < arr[mid]) {
            //向左边递归
            return binarySearch2(arr, val, left, mid - 1);
        } else if (val > arr[mid]) {
            //向右边递归
            return binarySearch2(arr, val, mid + 1, right);
        } else {

            List<Integer> resIndexList = new ArrayList<>();

            int temp = mid - 1;
            //左边没找到
            while (temp >= 0 && arr[temp] == val) {
                resIndexList.add(temp--);
            }
            resIndexList.add(mid);
            temp = mid + 1;
            while (temp <= arr.length - 1 && arr[temp] == val) {
                resIndexList.add(temp++);
            }
            return resIndexList;
        }
    }
}
